A typical conventional computer system includes an out-of-order central processing unit ("CPU"), a non-blocking cache subsystem, and a pipelined bus interface unit ("BIU"). During operation, a read or write request from the CPU is first sent to the cache. If the cache contains the target data (i.e., on a cache hit), the cache directly services the request. Conversely, if the cache does not contain the target data (i.e., on a cache miss) or if the request is directed to an uncacheable memory address or an input/output ("I/O") address, the cache passes the request on to the BIU. When the BIU receives a read or write request, the request is submitted to the external memory or I/O systems using a predefined bus protocol, and any results are returned back to the cache and CPU (via the cache). Additionally, the cache services snoop requests from external agents such as other processors in order to perform cache-coherency operations.
One bus protocol used in modern computer systems is the Pentium.RTM. II bus protocol as defined in Volume 1 of the Pentium Pro Family Developer's Manual, which is published by Intel Corporation (Santa Clara, Calif.) and is herein incorporated by reference. In accordance with this protocol, the BIU communicates with the memory and I/O systems using several different read and write request transaction formats including: bus read line ("BRL"), bus read and invalidate line ("BRIL"), bus invalidate line ("BIL"), bus write line ("BWL"), bus read partial ("BRP"), bus write partial ("BWP"), I/O read ("IOR"), and I/O write ("IOW"). A brief description of each of these transactions will now be given.
A bus read line transaction is requested when a new line is to be loaded into the cache. When a CPU read from a cacheable address misses the cache, the cache issues a BRL transaction to the BIU. In response, the BIU makes a read request to main memory for the number of bytes required to fill a cache line (e.g., 32 bytes). Because the CPU can process read transactions speculatively and out-of-order, BRLs do not have any ordering requirements either with respect to each other or with respect to other types of bus transactions.
A bus read and invalidate line transaction is initiated when a CPU write transaction to a cacheable address misses the cache. Like a BRL, a BRIL causes the BIU to read a line from external memory. Additionally, the addressed line is invalidated in all other caches (for external agents in the system) in which the line resides. Although in conventional systems memory writes must generally be kept in order, a BRIL does not directly influence the ordering of the CPU write transaction from which it was generated. Thus, BRILs do not have any ordering requirements either with respect to each other or with respect to other types of bus transactions. Similarly, a bus invalidate line transaction is initiated when a CPU write to a cacheable address hits a shared line in the cache. Such a shared line must be changed to the exclusive state before it can be modified by the CPU. The BIL transaction is used to invalidate the addressed line in all other caches in which the line resides, without reading any data from the external memory. BILs also do not have any ordering requirements either with respect to each other or with respect to other types of bus transactions.
A bus write line transaction is generated when the cache writes a displaced cache line back to memory so that a new line can be loaded into the cache. A BWL is also generated when multiple CPU write transactions to uncacheable memory addresses are accumulated (i.e., write-combined) in the BIU. In a BWL, an entire line (e.g., 32 bytes) is written to the external memory. Like BRLs, BWLs do not have any ordering requirements either with respect to each other or with respect to other types of bus transactions.
The bus read partial and I/O read transactions are generated when the CPU issues a read transaction that is directed to an uncacheable memory address or an I/O address, respectively. When a BRP or an IOR is submitted to the bus by the BIU, one to eight bytes of data are read from the designated address. Similarly, the bus write partial I/O write transactions are generated when the CPU issues a write transaction to an uncacheable memory address or an I/O address. The BWP and IOW transactions cause one to eight bytes of data to be written to the designated address. While the BIU must issue BRPs, BWPs, IORs, and IOWs to the bus in the order in which they are received from the CPU, these types of transactions do not have any ordering requirements with respect to BRLs, BRILs, BILs, and BWLs.
Because speculative out-of-order instruction execution is supported, the CPU can send a memory read request to the cache before receiving the results of previously-sent read requests. In other words, out-of-order execution of memory-referencing instructions can cause many CPU read requests to be simultaneously outstanding (i.e., waiting for data). Similarly, when the requested data is not in the cache, the non-blocking cache can send the read request on to the BIU without waiting for the completion of previously-sent read requests. In order to manage this out-of-order data flow, the CPU includes a memory shelf unit that sends read requests to the cache and stores information relating to outstanding read requests.
The conventional memory shelf has an entry for each incomplete CPU read request to identify the instruction awaiting the requested data When the cache (on a cache hit) or BIU (on a cache miss) returns data to the CPU, the identity of the instruction that requested the data must also be provided to the memory shelf so that the instruction can be rescheduled by the CPU. For this purpose, each read request issued by the memory shelf is given a numeric identifier, which is known as a read identifier ("RID"). The memory shelf sends an RID to the cache along with each new CPU read request, and the cache and BIU keep track of the RIDs of all read requests being processed. When a read request is completed, its RID is returned to the memory shelf along with the requested data so that the memory shelf can identify which instruction requested the data.
Additionally, regardless of the actual amount of data requested by a cacheable read transaction (e.g., from 1 to 8 bytes), the typical BIU always requests a line of data (i.e., the smallest amount of data that can be loaded into the cache) from external memory. Thus, whenever multiple read requests from the memory shelf request data from the same cache line, the BIU can combine the requests into a single bus transaction. The BIU compares the addresses of newly-received read requests with the address ranges of all incomplete read requests, which are stored in a transaction buffer known as the bus request queue ("BRQ"). If the address of a new read request falls within the address range of a data line already being retrieved from memory, the new read request is discarded. In this manner, multiple read requests of arbitrary size are "collapsed" into a single BRL in order to avoid the issuance of redundant bus transactions.
While the collapsing of CPU read requests increases the efficiency of the system bus, this feature presents a problem in systems having a non-blocking cache. In particular, after the BIU obtains a line of data that includes data for multiple CPU read requests, the memory shelf must be informed that the data for all of those read requests is available so that the corresponding instructions can be rescheduled. However, in the conventional collapsing process described above, the BIU simply discards all new read requests that fall within the address range of a data line already being retrieved. Thus, the BIU only stores the RID of the CPU read request that initiated the BRL, and only that RID can be provide to the memory shelf. In other words, after retrieving a line of data from memory, the BIU cannot return the RIDs for all read requests that were awaiting the data from that line.
Several tactics for overcoming this problem have been proposed. According to one approach, the BIU is prevented from simultaneously processing more than one read request. Once a CPU read request misses the cache, all subsequent read requests that miss the cache are suspended until the first request is completed. The memory shelf must later reissue all read requests that were suspended. While this approach properly returns all RIDs to the memory shelf, it also completely eliminates the concurrent processing of CPU read requests by the BIU. Another approach is to provide extra data fields in each BRQ entry so that multiple RIDs can be stored with each bus transaction. This allows multiple RIDs to be identified with a single bus transaction but sets a physical limit on the number of CPU read requests that can be collapsed into each transaction.
Yet another approach is to have the memory shelf keep track of all CPU read requests that are waiting for the same line to be retrieved from memory. After the memory shelf sends a CPU read request that accesses a particular cache line, subsequent requests for data from the same line are merely linked with the sent request in the memory shelf (e.g., using pointers). Then, when the RID for the sent request is returned, the memory shelf causes that request and all internally linked requests to be reissued. Thus, the memory shelf unit of the CPU becomes responsible for the collapsing of CPU read requests into a single bus transaction.